\section{Our technique}

The technique described in this paper was developed as part of
\sicl{}.%
\footnote{The \sicl{} repository is public, and it is currently
  located at https://github.com/robert-strandh/SICL.}  The system is
written entirely in \cl{}, and it was designed to be bootstrapped 
from a conforming \cl{} implementation including \clos{}.  
According to Rhodes \cite{Rhodes:2008:SSC:1482373.1482380}, few \cl{}
implementations are designed to be bootstrapped this way.  Instead,
most implementations evolve by incremental modifications to an
existing binary image.

A generic function in \sicl{} contains a \emph{cache} (a \emph{call
  history} in \sicl{} terminology) which associates classes of
required arguments with corresponding effective methods, as
specifically allowed by the AMOP.  The discriminating function of
every standard generic function contains two parts: one part computed
from the call history and a second \emph{default} part, invoked when
the first part fails.  This second part of the discriminating function
invokes the complete machinery defined by
\texttt{compute-applicable-methods-using-classes},
\texttt{compute-applicable-methods}, and
\texttt{compute-effective-method}.  Crucially, the first part is a
relatively simple mechanical translation from a set of call-history
entries to an \emph{automaton} that implements the dispatch.  This
translation requires none of the machinery for computing effective
methods. 

As hinted in the previous section, metastability issues can be handled
automatically, provided that:

\begin{itemize}
\item The call history contains entries for every combination of
  classes of required arguments such that:
  \begin{enumerate}
  \item the classes are specified by the AMOP, and 
  \item there is at least one primary applicable method for the
    combination.
  \end{enumerate}
\item When the class hierarchy changes, an entry in the call history
  is removed only if it involves a modified class.
\item When a method is removed from a generic function (possibly
  because it was replaced with a new one with the same specializers),
  an entry in the call history is removed only if it involves the
  method that was removed.
\end{itemize}

The reason that these conditions automatically handle
metastability issues is that the AMOP specifically disallows
modifications to specified classes.  Then the first part of the
discriminating function (i.e., the part computed from the call
history) will always handle invocations where classes of required
arguments are specified classes, including the function
\texttt{compute-discriminating-function}. 

Our technique, called \emph{satiation}, makes sure that the
conditions are met by trying every combination of existing classes as
the required arguments of every existing generic function in order to
see whether this combination corresponds to an applicable primary
method of the generic function.  If that is the case, then a
corresponding effective method is computed, and an entry is added to
the call history.  Finally, the resulting discriminating function is
computed.  Clearly, these computations require a fully-functional
machinery for precisely the functions that are being processed. 

While it may seem like overkill and an excessive amount of work to
compute call history entries for all possible combinations, this work
is justified because:

\begin{itemize}
\item The satiation machinery is invoked only during bootstrapping, so
  it does not affect performance at runtime. 
\item When the machinery is invoked, only a handful of classes and
  generic functions exist.  Therefore, the total amount of work is
  fairly small.
\end{itemize}

While it may be possible to invoke the satiation machinery
\emph{lazily} during bootstrapping,%
\footnote{It can not be invoked lazily at runtime, because then we
  would be back in a situation with metastability issues.}
there is not much to gain by doing that due to the limited amount of
work involved.  Furthermore, it would still be necessary to make sure
that the call history of each specified generic function contains all
entries required to avoid metastability issues at runtime, and that
work is identical to what the full machinery is designed to
accomplish. 

Now, in a system where \clos{} must be bootstrapped from a pre-\clos{}
implementation, satiation would require specialized code in the form
of ordinary functions (as opposed to generic functions) that do the
same work as the specified generic functions on arguments that are
instances of specified classes, with much duplicated code as a result.

An object in \sicl{} is either an \emph{immediate object}, a
\emph{\texttt{cons} cell}, or a \emph{general instance}.  A general
instance is represented as a two-word header where the first word
contains the \emph{class} of the instance, and the second word
contains the \emph{rack}.  When the instance is a standard object, the
rack holds the values of the \emph{slots} of the instance.  But
general instances are also used for instances of built-in classes, so
(for example) an instance of an array would have a rack that contains
storage for the elements of the array. 

In \sicl{}, we bootstrap \clos{} on an existing conforming \cl{}
implementation (the host) as follows:%
\footnote{The description of the bootstrapping procedure is simplified
  to avoid clutter.  In reality, there are several complications that
  need to be taken care of.}

\begin{enumerate}
\item First we use the definitions of the MOP classes to create
  ordinary host classes, albeit with names in a separate package.
  Slots with associated accessors will generate ordinary host generic
  functions. 
\item Next, we create \emph{bridge classes} and \emph{bridge generic
  functions}.  A bridge class is a host instance of one of the host
  classes created in phase 1.  A bridge generic function is an
  instance of the host class \texttt{standard-generic-function}
  created in phase 1, but also of the host class named
  \texttt{funcallable-standard-object}.%
  \footnote{The class \texttt{funcallable-standard-object} is not part
    of the \cl{} standard.  This is one of the few situations where
    bootstrapping \sicl{} requires some functionality that is not part
    of the standard.  We attempted to use the class
    \texttt{standard-generic-function} instead, but a major problem
    with that solution is the conflicting use of specified
    initialization arguments which are interpreted both by the host
    class and the bridge class.}
\item Third, we use bridge classes and bridge generic functions to
  create \emph{ersatz classes} and \emph{ersatz generic functions} as
  instances of the bridge classes previously created.  These are
  target instances represented as a combination of a host
  \emph{structure} for the header, and a host \emph{simple vector} for
  the rack.  At this stage the class slot of the header of an ersatz
  object contains a bridge class.
\item The graph of ersatz objects is then \emph{tied} by
  replacing every bridge class in the class slots of every ersatz
  object by its equivalent ersatz class, creating a complete graph of
  only ersatz objects. 
\item Finally, we traverse the graph of ersatz objects in order to
  create an isomorphic graph as a sequence of bytes to become the
  memory image of the target system.
\end{enumerate}

In the vast majority of cases, the same definitions of functions and
classes is used to create host objects in phase 1, bridge objects in
phase 2, and ersatz objects in phase 3. 

The discriminating function of each bridge generic function is
computed using the full machinery executing as a set of host generic
functions.  This includes the satiation machinery so that the call
history of each bridge generic function is completely pre-computed.
Similarly, the discriminating function of each ersatz generic function
is computed using the full machinery executing as a set of bridge
generic functions.  

The end result is a memory image containing all the generic functions
specified by the AMOP, and each of these generic functions has the following
characteristics:

\begin{itemize}
\item The call history contains pre-computed effective methods for all
  combinations of specified classes that result in at least one primary
  applicable method.
\item When a specified generic function \texttt{F} is invoked with
  itself or some other specified generic function as an argument, then
  the effective method for handling the call already exists in the
  call history of \texttt{F}. 
\item Since the AMOP specifically disallows modifications to specified
  classes after their initial definitions, call-history entries
  involving specified classes will always be valid.
\item Call-history entries involving specified classes are not removed
  as a result of methods being added or removed in conformance with
  the AMOP, nor as a result of valid modifications of existing
  classes. 
\item The call history is translated into a discriminating function
  without invoking the machinery for computing effective methods. 
\end{itemize}

This combination of characteristics guarantees the absence of
metastability issues at runtime.

%%  LocalWords:  metastability specializer specializers accessor
%%  LocalWords:  accessors funcallable
